/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  //定义一个数组res：存储所有合法的括号组合
  let res = []
  //定义一个递归函数：计算所有合法的括号组合
  function backTrack(left, right, path) {
    //如果左、右括号都用完了，说明找到了一个合法的括号组合：将该组合放入数组res，返回
    if (left === 0 && right === 0) {
      res.push(path)
      return
    }
    //只要还有左括号，优先对加左括号的操作进行dfs
    if (left > 0) backTrack(left - 1, right, path + '(')
    //右括号多余左括号时（保证生成的数组组合合法），再对加左括号的操作进行dfs
    if (right > left) backTrack(left, right - 1, path + ')')
  }
  //调用递归函数
  backTrack(n, n, '')
  //返回数组res
  return res
}
console.log(generateParenthesis(3))